<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4464：[Jsoi2013]旅行时的困惑</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Jsoi2013]旅行时的困惑</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Jsoi2013]旅行时的困惑</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Jsoi2013]旅行时的困惑                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>Waldives 有 N 个小岛。目前的交通系统中包含 N-1 条快艇专线，每条快艇<br />
专线连接两个岛。这 N-1条快艇专线恰好形成了一棵树。 <br />
由于特殊的原因，所有N-1条快艇专线都是单向的。这导致了很多岛屿之间<br />
不能相互到达。因此，Waldives 政府希望新建一些公交线路，使得建设完毕后，<br />
任意两个小岛都可以互相到达。为了节约开支，政府希望建设最少的公交线路。&nbsp; <br />
同时，出于规划考虑，每一条公交线路都有如下的要求： <br />
1、每一条交通线路包含若干条连续的快艇专线，你可以认为一条公交线路<br />
对应树上的一条路径，而其所包含的若干快艇专线则对应树上被这条路<br />
径所覆盖的树边（也就是之前已经存在的某个快艇专线）； <br />
2、显然一条交通线路只能覆盖树上任意一条边至多一次； <br />
3、公交线路中所包含的每一个快艇专线都是有方向的，并且与其所覆盖的<br />
树边的方向相反； <br />
4、不同的公交线路可以覆盖树上相同的点或者相同的边。 <br />
Waldives 的 N 个岛屿分别从 0 到 N-1 编号。现在给出 Waldives 已有的快艇<br />
专线信息，请计算最少所需要新建的交通线路的数量。</p></p><hr/><h3>输入格式</h3><p><p>第一行包含一个整数 N。 接下来 N-1行，每行包含两个整数 x，y。表示存在一条从岛屿 x开往岛屿y的快艇专线。 N &lt; = 100000</p></p><hr/><h3>输出格式</h3><p><p>输出一行一个整数，表示需要建设的最少的交通线路数量。</p></p><hr/><h3>样例输入</h3><pre>4
0 1
1 2
1 3</pre><hr/><h3>样例输出</h3><pre>2</pre><hr/><h3>提示</h3><p><p>样例如下图所示。图中给出了一个可行的最佳方案。<br />
其中黑色的实边代表原先已经存在的快艇专线， 而虚边则对新加入的公交线<br />
路，分别为 2-&gt;1-&gt;0和3-&gt;1-&gt;0。<br />
注意直接新建公交线路 3-&gt;2 是不允许的，这并不是一条树上的合法路径，<br />
因为编号为3的点与编号为1的点在树中并不直接相连。同样的，建立公交路线<br />
2-&gt;1-&gt;3也是不允许的，因为这条路线中包含快艇专线1-&gt;3，这并没有和已有的<br />
专线的方向相反<br />
<img width="173" height="209" src="../file/4464_0.png" alt="" /></p>
<p>题解:<a href="/JudgeOnline/upload/201604/sol.rar">JudgeOnline/upload/201604/sol.rar</a></p></p><hr/><h3>题目来源</h3><p>By 佚名上传</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4464" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4464" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>